package Hash;

import java.util.*;

public class LkTest {
    /*给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c2 。
    * */
    public boolean judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) {
            double b = Math.sqrt(c - a * a);
            if (b == (int) b) {
                return true;
            }
        }
        return false;
    }
    /*
    * 给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。*/
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set= new HashSet<>();
        HashSet<Integer> set2= new HashSet<>();
        for (int k:nums1) {
            set.add(k);
        }
        for (int k:nums2) {
            if (set.contains(k)){
               set2.add(k);
            }
        }
        int[] arr = new int[set2.size()];
        Iterator<Integer> s= set2.iterator();
        int i =0;
      while (s.hasNext()){
          arr[i] = s.next();
          i++;
      }
        return arr;
    }
    /*给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
    请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
    解法: 先用哈希set去重,然后如果一个数-1在哈希表中, 就跳过, 否则就去看它+1的数是否在哈希表中*/
    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }
        int ans = 0;
        for (int num : num_set) {
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                ans = Math.max(ans, currentStreak);
            }
        }

        return ans;
    }
    /*编写一个算法来判断一个数 n 是不是快乐数。*/

    private int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }

    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
    /* 判断键盘输入的字符串是不是同意行的*/
    public String[] findWords(String[] words) {
        List<String>ans=new ArrayList<>();
        String str1="qwertyuiopQWERTYUIOP";
        String str2="asdfghjklASDFGHJKL";
        String str3="zxcvbnmZXCVBNM";
        Set<Character>set1=new HashSet<>();
        Set<Character>set2=new HashSet<>();
        Set<Character>set3=new HashSet<>();
        for(int i=0;i<str1.length();++i) set1.add(str1.charAt(i));
        for(int i=0;i<str2.length();++i) set2.add(str2.charAt(i));
        for(int i=0;i<str3.length();++i) set3.add(str3.charAt(i));

        for(String word:words){
            int n1=0,n2=0,len=word.length();
            char cc=word.charAt(0);
            // 看第一个字母是那行
            if(set1.contains(cc)) {n1=1;n2=n1;}
            else if(set2.contains(cc)) {n1=2;n2=n1;}
            else if(set3.contains(cc)) {n1=3;n2=n1;}

            for(int i=1;i<len&&n1==n2;++i){
                char c=word.charAt(i);
                if(set1.contains(c)) n2=1;
                else if(set2.contains(c)) n2=2;
                else if(set3.contains(c)) n2=3;
            }
            if(n1==n2){
                ans.add(word);
            }
        }
        return ans.toArray(new String[ans.size()]);
    }
    /*给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。*/
    public boolean wordPattern(String pattern, String str) {
        String[] words = str.split(" ");
        //字符和单词是互相映射，数量必须相等
        if (words.length != pattern.length()) {
            return false;
        }
        Map<Object, Integer> map = new HashMap<>();
        for (Integer i = 0; i < words.length; i++) {
            /*
                如果key不存在，插入成功，返回null；如果key存在，返回之前对应的value。

                以pattern = "abba", str = "dog cat cat dog"为例，
                第1次：map.put('a',0)返回null，map.put("dog",0)返回null，两者相等；
                第2次：map.put('b',1)返回null，map.put("cat",1)返回null，两者相等；
                第3次：map.put('b',2)返回1，map.put("cat",2)返回1，两者相等；
                第4次：map.put('a',3)返回0，map.put("dog",3)返回0，两者相等，
                结果为 true。
            */
            if (map.put(pattern.charAt(i), i) != map.put(words[i], i)) {
                return false;
            }
        }
        return true;
    }


    public int findPairs(int[] nums, int k) {
        Set<Integer> visited = new HashSet<Integer>();
        Set<Integer> res = new HashSet<Integer>();
        for (int num : nums) {
            if (visited.contains(num - k)) {
                res.add(num - k);
            }
            if (visited.contains(num + k)) {
                res.add(num);
            }
            visited.add(num);
        }
        return res.size();
    }
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> s2t = new HashMap<Character, Character>();
        Map<Character, Character> t2s = new HashMap<Character, Character>();
        int len = s.length();
        for (int i = 0; i < len; ++i) {
            char x = s.charAt(i), y = t.charAt(i);
            if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
                return false;
            }
            s2t.put(x, y);
            t2s.put(y, x);
        }
        return true;
    }
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head) {
        HashMap<Node,Node> hashMap = new HashMap<>();
        Node cur = head;
        while (cur != null){
            hashMap.put(cur,new Node(cur.val));
            cur =cur.next;
        }
        cur = head;
        Node newNode = new Node(-1);
        Node ret = newNode;
        while (cur != null){
            hashMap.get(cur).random = hashMap.get(cur.random);
            ret.next = hashMap.get(cur);
            ret=ret.next;
            cur =cur.next;
        }
        return newNode.next;

    }






}
